/*
    归并排序

    前置知识：讲解019-算法笔试中处理输入和输出、讲解020-递归和master公式

    1）左部分排好序、右部分排好序、利用merge过程让左右整体有序
    2）merge过程：谁小拷贝谁，直到左右两部分所有的数字耗尽，拷贝回原数组
    3）递归实现和非递归实现
    4）时间复杂度O(n * logn)
    5）需要辅助数组，所以额外空间复杂度O(n)
    6）归并排序为什么比O(n^2)的排序快？因为比较行为没有浪费！
    7）利用归并排序的便利性可以解决很多问题 - 归并分治 - 下节课
    注意：
    有些资料说可以用原地归并排序，把额外空间复杂度变成O(1)，不要浪费时间去学
    因为原地归并排序确实可以省空间，但是会让复杂度变成O(n^2)
    有关排序更多的概念、注意点、闭坑指南，将在后续课程继续

*/